#include <algorithm>
#include <sstream>
#include "assistant.h"
#include "cstdlib"
#include <cfloat>
#include <iostream>
#include <unordered_set>

using namespace std;


// 去除字符串中头尾属于  cutset 中的字符
void trim(string& s, string cutset)
{
	unordered_set<char> charSet;
	for (char c : cutset)
		charSet.insert(c);

	// 去除头部
	int head = s.size();  // 第一个不属于 cutset 字符集的字符所在的位置
	for (int i = 0; i < s.size(); i++)
	{
		if (charSet.count(s[i]) > 0)
			continue;
		else
		{
			head = i;
			break;
		}
	}

	// 去除尾部
	int tail = -1;
	for (int i = s.size() - 1; i >= 0; i--)
	{
		if (charSet.count(s[i]) > 0)
			continue;
		else
		{
			tail = i;
			break;
		}
	}

	if (head > tail)
		s = "";
	else
		s = s.substr(head, tail - head + 1);
}


/* 注意该文件前面不能有空行，如果有空行的话，getline 函数会将空行当作一个正常行进行处理 */
vector<int> init_fac_id(string file_name, int line_id)
{
	vector<int> res;
	ifstream fin(file_name);
	if (fin.is_open())
	{
		string temp_str;
		/* 读入前面不需要的数行，当然这里其实可以只读入一次并缓存，然后后面的调用请求，直接读取缓存 */
		for (int i = 1; i <= line_id; i++)
		{
			getline(fin, temp_str);
		}
		trim(temp_str, " \t\n");  // 去除头尾的空字符

		vector<int> space_index;  // 记录空字符所在的位置
		space_index.push_back(-1);
		char* cStr = new char[temp_str.size() + 1];  // 记录转换为 c 字符串的数据
		for (int i = 0; i < temp_str.size(); i++)
		{
			if (temp_str[i] == ' ')
			{
				cStr[i] = '\0';
				space_index.push_back(i);
			}
			else
				cStr[i] = temp_str[i];
		}
		cStr[temp_str.size()] = '\0';

		for (auto i : space_index)
		{
			res.push_back(atoi(cStr + i + 1));
		}

		delete[] cStr;
	}
	else
	{
		std::cerr << "打开 fac_id.txt 文件失败\n";
		exit(1);
	}

	return res;
}


static unordered_map<string, double> fac2dist;  // 记录设施 id 到最终距离的映射，防止重复计算
double calculate_original_dist(unordered_map<int, unordered_map<int, double>>& distance, vector<int>& fac_id, unordered_map<int, int>& visit_num)
{
	visit_num.clear();

	double res = 0.0;
	for (int i = 0; i < distance.size(); i++)  // 遍历每个用户
	{
		int pre_id;
		double pre_dist = DBL_MAX;
		for (auto j : fac_id)  // 遍历每个距离
		{
			if (distance[i][j] < pre_dist)
			{
				pre_dist = distance[i][j];
				pre_id = j;
			}
		}
		res += pre_dist;
		visit_num[pre_id]++;
	}

	// 记录这个设施集对应的最终距离
	sort(fac_id.begin(), fac_id.end());
	stringstream ss;
	for (int i : fac_id)
	{
		ss << i << ",";
	}
	fac2dist[ss.str()] = res;

	return res;
}


double calculate_original_dist(std::unordered_map<int, std::unordered_map<int, double>>& distance, std::vector<int>& fac_id)
{
	sort(fac_id.begin(), fac_id.end());
	stringstream ss;
	for (auto i : fac_id)
	{
		ss << i << ",";
	}
	if (fac2dist.count(ss.str()))
		return fac2dist[ss.str()];

	double res = 0.0;
	for (int i = 0; i < distance.size(); i++)  // 遍历每个用户
	{
		int pre_id;
		double pre_dist = DBL_MAX;
		for (auto j : fac_id)  // 遍历每个距离
		{
			if (distance[i][j] < pre_dist)
			{
				pre_dist = distance[i][j];
				pre_id = j;
			}
		}
		res += pre_dist;
	}

	fac2dist[ss.str()] = res;
	return res;
}


double calculate_original_dist(std::unordered_map<int, std::unordered_map<int, double>>& distance, std::map<int, double>& fac_id)
{
	/* 首先判断是否已经记录 */
	stringstream ss;
	for (auto& p : fac_id)
	{
		ss << p.first << ",";
	}
	if (fac2dist.count(ss.str()))
		return fac2dist[ss.str()];

	/* 没有记录 */
	double res = 0.0;
	for (int i = 0; i < distance.size(); i++)  // 遍历每个用户
	{
		int pre_id;
		double pre_dist = DBL_MAX;
		for (auto& p : fac_id)  // 遍历每个距离
		{
			if (distance[i][p.first] < pre_dist)
			{
				pre_dist = distance[i][p.first];
				pre_id = p.first;
			}
		}
		res += pre_dist;
	}
	fac2dist[ss.str()] = res;
	return res;
}


double calculate_original_dist(std::unordered_map<int, std::unordered_map<int, double>>& distance, std::unordered_set<int>& fac_id)
{
	/* 首先判定是否已经计算过了 */
	std::vector<int> temp;
	for (auto i : fac_id)
		temp.push_back(i);
	sort(temp.begin(), temp.end());
	stringstream ss;
	for (auto i : temp)
		ss << i << ",";
	if (fac2dist.count(ss.str()))
		return fac2dist[ss.str()];

	/* 距离没有存储过 */
	double res = 0.0;
	for (int i = 0; i < distance.size(); i++)  // 遍历每个用户
	{
		double pre_dist = DBL_MAX;
		for (auto j : fac_id)  // 遍历每个距离
		{
			if (distance[i][j] < pre_dist)
			{
				pre_dist = distance[i][j];
			}
		}
		res += pre_dist;
	}

	fac2dist[ss.str()] = res;
	return res;
}
